{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Earliest Moment When Everyone Become Friends"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: earliestAcq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #彼此熟识的最早时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个社交圈子当中，有&nbsp;<code>n</code>&nbsp;个人。每个人都有一个从&nbsp;<code>0</code> 到&nbsp;<code>n - 1</code>&nbsp;的唯一编号。我们有一份日志列表&nbsp;<code>logs</code>，其中&nbsp;<code>logs[i] = [timestamp<sub>i</sub>, x<sub>i</sub>, y<sub>i</sub>]</code>&nbsp;表示 <code>x<sub>i</sub></code>&nbsp;和&nbsp;<code>y<sub>i</sub></code>&nbsp;将在同一时间&nbsp;<code>timestamp<sub>i</sub></code><sub>&nbsp;</sub>成为朋友。</p>\n",
    "\n",
    "<p>友谊是 <strong>相互</strong> 的。也就是说，如果 <code>a</code> 和 <code>b</code> 是朋友，那么&nbsp;<code>b</code>&nbsp;和 <code>a</code> 也是朋友。同样，如果 <code>a</code> 和 <code>b</code> 是朋友，或者&nbsp;<code>a</code> 是 <code>b</code> 朋友的朋友 ，那么 <code>a</code> 和 <code>b</code> 是熟识友。</p>\n",
    "\n",
    "<p>返回圈子里所有人之间都熟识的最早时间。如果找不到最早时间，就返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], N = 6\n",
    "<strong>输出：</strong>20190301\n",
    "<strong>解释：</strong>\n",
    "第一次结交发生在 timestamp = 20190101，0 和 1 成为好友，社交朋友圈如下 [0,1], [2], [3], [4], [5]。\n",
    "第二次结交发生在 timestamp = 20190104，3 和 4 成为好友，社交朋友圈如下 [0,1], [2], [3,4], [5].\n",
    "第三次结交发生在 timestamp = 20190107，2 和 3 成为好友，社交朋友圈如下 [0,1], [2,3,4], [5].\n",
    "第四次结交发生在 timestamp = 20190211，1 和 5 成为好友，社交朋友圈如下 [0,1,5], [2,3,4].\n",
    "第五次结交发生在 timestamp = 20190224，2 和 4 已经是好友了。\n",
    "第六次结交发生在 timestamp = 20190301，0 和 3 成为好友，大家都互相熟识了。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4\n",
    "<strong>输出:</strong> 3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= logs.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>logs[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= timestamp<sub>i</sub>&nbsp;&lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub>&nbsp;&lt;= n - 1</code></li>\n",
    "\t<li><code>x<sub>i</sub>&nbsp;!= y<sub>i</sub></code></li>\n",
    "\t<li><code>timestamp<sub>i</sub></code>&nbsp;中的所有时间戳&nbsp;<strong>均</strong><strong>不同</strong></li>\n",
    "\t<li>所有的对 <code>(xi, yi)</code> 在输入中最多出现一次</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-earliest-moment-when-everyone-become-friends](https://leetcode.cn/problems/the-earliest-moment-when-everyone-become-friends/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-earliest-moment-when-everyone-become-friends](https://leetcode.cn/problems/the-earliest-moment-when-everyone-become-friends/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]]\\n6', '[[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findRoot(self, node):\n",
    "        while self.root[node] != node:\n",
    "            self.root[node] = self.root[self.root[node]]\n",
    "            node = self.root[node]\n",
    "        return node\n",
    "\n",
    "    def unite(self, node1, node2):\n",
    "        root1, root2 = self.findRoot(node1), self.findRoot(node2)\n",
    "        if root1 == root2:\n",
    "            return\n",
    "        if self.size[root1] >= self.size[root2]:\n",
    "            bigRoot, smallRoot = root1, root2\n",
    "        else:\n",
    "            bigRoot, smallRoot = root2, root1\n",
    "        self.root[smallRoot] = bigRoot\n",
    "        self.size[bigRoot] += self.size[smallRoot]\n",
    "        self.setCount -= 1\n",
    "    \n",
    "    def isConnected(self, node1, node2):\n",
    "        return findRoot(node1) == findRoot(node2)\n",
    "        \n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        logs.sort()\n",
    "        for timepoint, x, y in logs:\n",
    "            uf.unite(x, y)\n",
    "            if uf.setCount == 1:\n",
    "                return timepoint\n",
    "        \n",
    "        return -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        \n",
    "        p={i:i for i in range(n)}\n",
    "        rank=[1]*n\n",
    "        def find(x):\n",
    "            if p[x]==x:\n",
    "                return p[x]\n",
    "            p[x]=find(p[x])\n",
    "            return p[x]\n",
    "        def union(x,y):\n",
    "            fx=find(x)\n",
    "            fy=find(y)\n",
    "            p[fx]=fy\n",
    "            rank[fy]+=rank[fx]\n",
    "        logs.sort()\n",
    "        for t,s,e in logs:\n",
    "            a=find(s)\n",
    "            b=find(e)\n",
    "            if a!=b:\n",
    "                union(s,e)\n",
    "                #print(rank,s,e)\n",
    "                #print(p)\n",
    "                if rank[b]==n:\n",
    "                    return t\n",
    "\n",
    "        return -1\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        # 为了确保找到最早的时刻\n",
    "        # 首先，按时间顺序对事件进行排序\n",
    "        logs.sort(key = lambda x: x[0])\n",
    "\n",
    "        uf = UnionFind(n)\n",
    "        # 开始时，我们将每个人视为一个单独的群体\n",
    "        group_cnt = n\n",
    "\n",
    "        # 我们使用这个方法合并各组\n",
    "        for timestamp, friend_a, friend_b in logs:\n",
    "            if uf.union(friend_a, friend_b):\n",
    "                group_cnt -= 1\n",
    "\n",
    "            # 这是所有个体相互联系的时刻\n",
    "            if group_cnt == 1:\n",
    "                return timestamp\n",
    "\n",
    "        # 还剩下不止一组\n",
    "        # 即不是每个人都连接\n",
    "        return -1\n",
    "class UnionFind:\n",
    "\n",
    "    def __init__(self, size):\n",
    "        self.group = [group_id for group_id in range(size)]\n",
    "        self.rank = [0] * size\n",
    "\n",
    "    def find(self, person):\n",
    "        if self.group[person] != person:\n",
    "            self.group[person] = self.find(self.group[person])\n",
    "        return self.group[person]\n",
    "\n",
    "    def union(self, a, b):\n",
    "        group_a = self.find(a)\n",
    "        group_b = self.find(b)\n",
    "        is_merged = False\n",
    "        if group_a == group_b:\n",
    "            return is_merged\n",
    "\n",
    "        is_merged = True\n",
    "        # 将低级别组合并到高级别组中。\n",
    "        if self.rank[group_a] > self.rank[group_b]:\n",
    "            self.group[group_b] = group_a\n",
    "        elif self.rank[group_a] < self.rank[group_b]:\n",
    "            self.group[group_a] = group_b\n",
    "        else:\n",
    "            self.group[group_a] = group_b\n",
    "            self.rank[group_b] += 1\n",
    "\n",
    "        return is_merged\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        logs.sort()\n",
    "        p = [*range(n)]\n",
    "        def find(i):\n",
    "            if p[i] != i:\n",
    "                p[i] = find(p[i])\n",
    "            return p[i]\n",
    "        for t, i, j in logs:\n",
    "            i1, j1 = find(i), find(j)\n",
    "            if i1 != j1:\n",
    "                if n == 2:\n",
    "                    return t\n",
    "                p[i1] = j1\n",
    "                n -= 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "      def find(x):\n",
    "        while root[x] != -1:\n",
    "          x = root[x]\n",
    "        return x\n",
    "      \n",
    "      logs.sort()\n",
    "      root = [-1] * n\n",
    "      for time, x, y in logs:\n",
    "        rootX, rootY = find(x), find(y)\n",
    "        if rootX == rootY:  continue\n",
    "        if root[rootX] == -1:\n",
    "          root[rootX] = rootY\n",
    "          n -= 1\n",
    "        else:\n",
    "          if root[rootY] == -1:\n",
    "            n -= 1\n",
    "          root[rootY] = rootX\n",
    "        if n == 1:  return time\n",
    "      return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        logs.sort()\n",
    "        p = [*range(n)]\n",
    "        def find(i):\n",
    "            if p[i] != i:\n",
    "                p[i] = find(p[i])\n",
    "            return p[i]\n",
    "        for t, i, j in logs:\n",
    "            if i > j:\n",
    "                i, j = j, i\n",
    "            i1, j1 = find(i), find(j)\n",
    "            if i1 != j1:\n",
    "                if n == 2:\n",
    "                    return t\n",
    "                p[i1] = j1\n",
    "                n -= 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        p = [x for x in range(n)]\n",
    "        size = [1] * n \n",
    "        def find(x) :\n",
    "            if p[x] != x: \n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def union(x, y) : \n",
    "            px, py = find(x), find(y)\n",
    "            if px == py :\n",
    "                return \n",
    "            p[px] = py\n",
    "            size[py] += size[px]\n",
    "        logs.sort()\n",
    "        for a, b, c in logs :\n",
    "            union(b, c)\n",
    "            if size[find(c)] == n :\n",
    "                return a \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        logs.sort()\n",
    "        for t, x, y in logs:\n",
    "            uf.union(x, y)\n",
    "            if uf.part == 1:\n",
    "                return t\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        logs.sort()\n",
    "        kkk=setUnion(n)\n",
    "        cnt=n\n",
    "        for time,i,j in logs:\n",
    "            kkk.union(i,j)\n",
    "            if kkk.setCount==1:\n",
    "                return time\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        logs.sort()\n",
    "        parent = [i for i in range(n)]\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(x, y):\n",
    "            parent[find(x)] = find(y)\n",
    "        for i in range(len(logs)):\n",
    "            time, a, b = logs[i][0], logs[i][1], logs[i][2]\n",
    "            union(a, b)\n",
    "            for i in range(n):\n",
    "                find(i)\n",
    "            if len(set(parent)) == 1:\n",
    "                return time\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        scnt = n \n",
    "        p = [i for i in range(n)]\n",
    "        logs.sort(key=lambda x:x[0]) \n",
    "        def find(x):\n",
    "            if x == p[x]:\n",
    "                return x \n",
    "            p[x] = find(p[x])\n",
    "            return p[x] \n",
    "        def un(x, y):\n",
    "            nonlocal scnt \n",
    "            fx, fy = find(x), find(y) \n",
    "            if fx ==fy:\n",
    "                return False \n",
    "            else:\n",
    "                p[fy] = fx \n",
    "                scnt -= 1\n",
    "                return True \n",
    "        for time, a, b in logs:\n",
    "            un(a, b) \n",
    "            if scnt == 1:\n",
    "                return time \n",
    "        return -1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], N: int) -> int:\n",
    "        p=[i for i in range(N)]\n",
    "        logs.sort(key=lambda x: x[0])\n",
    "\n",
    "        def find(x, p):\n",
    "            if x!=p[x]: return find(p[x], p)\n",
    "            else: return p[x]\n",
    "        \n",
    "        for l in logs:\n",
    "            p1, p2=find(l[1], p), find(l[2], p)\n",
    "            if p1==p2: continue\n",
    "            p[p1]=p2\n",
    "            N-=1\n",
    "            if N==1: return l[0]\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1]*n\n",
    "        self.part = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.root[x]:\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            root_x = self.find(self.root[x])\n",
    "            self.root[x] = root_x\n",
    "            return root_x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        logs = sorted(logs, key = lambda x: x[0])\n",
    "        uf = UnionFind(n)\n",
    "        for t, x, y in logs:\n",
    "            uf.union(x, y)\n",
    "            if uf.part == 1:\n",
    "                return t \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        \n",
    "        p={i:i for i in range(n)}\n",
    "        rank=[1]*n\n",
    "        def find(x):\n",
    "            if p[x]==x:\n",
    "                return p[x]\n",
    "            p[x]=find(p[x])\n",
    "            return p[x]\n",
    "        def union(x,y):\n",
    "            fx=find(x)\n",
    "            fy=find(y)\n",
    "            p[fx]=fy\n",
    "            rank[fy]+=rank[fx]\n",
    "        logs.sort()\n",
    "        for t,s,e in logs:\n",
    "            a=find(s)\n",
    "            b=find(e)\n",
    "            if a!=b:\n",
    "                union(s,e)\n",
    "                #print(rank,s,e)\n",
    "                #print(p)\n",
    "                if rank[b]==n:\n",
    "                    return t\n",
    "\n",
    "        return -1\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        fa=dict()\n",
    "        def find(x):\n",
    "            if x not in fa:\n",
    "                fa[x]=x\n",
    "            if x!=fa[x]:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(a,b):\n",
    "            fa[find(a)]=find(b)\n",
    "        logs.sort()\n",
    "        c=0\n",
    "        for t,a,b in logs:\n",
    "            #print(a,b,fa)\n",
    "            if find(a)==find(b):\n",
    "                continue\n",
    "            c+=1\n",
    "            if c==n-1:\n",
    "                return t\n",
    "            union(a,b)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.root = list(range(n))\n",
    "        self.size = [0] * n\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findRoot(self, node):\n",
    "        while self.root[node] != node:\n",
    "            self.root[node] = self.root[self.root[node]]\n",
    "            node = self.root[node]\n",
    "        return node\n",
    "    \n",
    "    def unite(self, node1, node2):\n",
    "        root1, root2 = self.findRoot(node1), self.findRoot(node2)\n",
    "        if root1 == root2:\n",
    "            return\n",
    "        if self.size[root1] >= self.size[root2]:\n",
    "            bigRoot, smallRoot = root1, root2\n",
    "        else:\n",
    "            bigRoot, smallRoot = root2, root1\n",
    "        \n",
    "        self.root[smallRoot] = bigRoot\n",
    "        self.size[bigRoot] += self.size[smallRoot]\n",
    "        self.setCount -= 1\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        logs.sort()\n",
    "\n",
    "        for timestamp, x, y in logs:\n",
    "            uf.unite(x, y)\n",
    "            if uf.setCount == 1:\n",
    "                return timestamp\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        logs.sort()\n",
    "        fa = [x for x in range(n)]\n",
    "        cnt = n\n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(p, q):\n",
    "            p, q = find(p), find(q)\n",
    "            if p == q: return\n",
    "            nonlocal cnt\n",
    "            cnt -= 1\n",
    "            fa[p] = q\n",
    "        for t, x, y in logs:\n",
    "            merge(x, y)\n",
    "            if cnt == 1:\n",
    "                return t\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, x) -> None:\n",
    "        self.uf = [-1] * x\n",
    "\n",
    "    def find(self, x):\n",
    "        r = x\n",
    "        while self.uf[x] >= 0:\n",
    "            x = self.uf[x]\n",
    "\n",
    "        while r != x:\n",
    "            self.uf[r], r = x, self.uf[r]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        ux, uy = self.find(x), self.find(y)\n",
    "        if ux == uy:\n",
    "            return\n",
    "        if self.uf[ux] >= self.uf[uy]:\n",
    "            self.uf[uy] += self.uf[ux]\n",
    "            self.uf[ux] = uy\n",
    "        else:\n",
    "            self.uf[ux] += self.uf[uy]\n",
    "            self.uf[uy] = ux\n",
    "        return\n",
    "\n",
    "    def count(self):\n",
    "        ans = 0\n",
    "        for c in self.uf:\n",
    "            if c < 0 and c != -1:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "    def valid(self):\n",
    "        n = len(self.uf)\n",
    "        for c in range(n):\n",
    "            if self.uf[c] == -n:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def __print__(self):\n",
    "        return self.uf\n",
    "    \n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        m = len(logs)\n",
    "        logs.sort()\n",
    "        uf = UnionFind(n)\n",
    "        for i in range(m):\n",
    "            t,x,y = logs[i]\n",
    "            uf.union(x,y)\n",
    "            if uf.valid():\n",
    "                return t\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, size):\n",
    "        self.parent = list(range(size))\n",
    "        self.rank = [0] * size\n",
    "        self.cnt = [1] * size\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])  # Path compression.\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x != root_y:\n",
    "            if self.rank[root_x] < self.rank[root_y]:\n",
    "                self.parent[root_x] = root_y\n",
    "                self.cnt[root_y] += self.cnt[root_x]\n",
    "            elif self.rank[root_x] > self.rank[root_y]:\n",
    "                self.parent[root_y] = root_x\n",
    "                self.cnt[root_x] += self.cnt[root_y]\n",
    "            else:\n",
    "                self.parent[root_y] = root_x\n",
    "                self.rank[root_x] += 1\n",
    "                self.cnt[root_x] += self.cnt[root_y]\n",
    "\n",
    "    # def is_connected(self, x, y):\n",
    "    #     return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_cnt(self, x):\n",
    "        root_x = self.find(x)\n",
    "        return self.cnt[root_x]\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        logs.sort(key=lambda x: x[0])\n",
    "        uf = UnionFind(n)\n",
    "        for ts, x, y in logs:\n",
    "            uf.union(x, y)\n",
    "            if uf.get_cnt(x) == n:\n",
    "                return ts\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        \n",
    "        p={i:i for i in range(n)}\n",
    "        rank=[1]*n\n",
    "        def find(x):\n",
    "            if p[x]==x:\n",
    "                return p[x]\n",
    "            p[x]=find(p[x])\n",
    "            return p[x]\n",
    "        def union(x,y):\n",
    "            p[find(x)]=find(y)\n",
    "            rank[find(y)]+=rank[find(x)]\n",
    "        logs.sort()\n",
    "        for t,s,e in logs:\n",
    "            a=find(s)\n",
    "            b=find(e)\n",
    "            if a!=b:\n",
    "                union(s,e)\n",
    "                ans=t\n",
    "        for x in p:\n",
    "            find(x)\n",
    "        if len(set(p.values()))!=1:\n",
    "\n",
    "            return -1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        # 首先，我们需要按时间顺序对这些事件进行排序。\n",
    "        logs.sort(key = lambda x: x[0])\n",
    "\n",
    "        uf = UnionFind(n)\n",
    "        # 最初，我们将每个人视为一个单独的群体。\n",
    "        group_cnt = n\n",
    "\n",
    "        # 我们使用这个方法合并各组。\n",
    "        for timestamp, friend_a, friend_b in logs:\n",
    "            if uf.union(friend_a, friend_b):\n",
    "                group_cnt -= 1\n",
    "\n",
    "            # 这是所有个体相互联系的时刻。\n",
    "            if group_cnt == 1:\n",
    "                return timestamp\n",
    "\n",
    "        # 还剩下不止一个群体，\n",
    "        # 也就是说，不是每个人都连接在一起。\n",
    "        return -1\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "\n",
    "    def __init__(self, size):\n",
    "        self.group = [group_id for group_id in range(size)]\n",
    "        self.rank = [0] * size\n",
    "\n",
    "    def find(self, person):\n",
    "        if self.group[person] != person:\n",
    "            self.group[person] = self.find(self.group[person])\n",
    "        return self.group[person]\n",
    "\n",
    "    def union(self, a, b):\n",
    "        # \"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\n",
    "        #     return: 如果 a 和 b 之前没有连接，则为 true\n",
    "        #             否则，将 a 与 b 连接，然后返回 false\n",
    "        # \"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\"\n",
    "        group_a = self.find(a)\n",
    "        group_b = self.find(b)\n",
    "        is_merged = False\n",
    "        if group_a == group_b:\n",
    "            return is_merged\n",
    "\n",
    "        is_merged = True\n",
    "        # 将低级别组合并到高级别组中。\n",
    "        if self.rank[group_a] > self.rank[group_b]:\n",
    "            self.group[group_b] = group_a\n",
    "        elif self.rank[group_a] < self.rank[group_b]:\n",
    "            self.group[group_a] = group_b\n",
    "        else:\n",
    "            self.group[group_a] = group_b\n",
    "            self.rank[group_b] += 1\n",
    "\n",
    "        return is_merged\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/the-earliest-moment-when-everyone-become-friends/solutions/2383084/bi-ci-shou-shi-de-zui-zao-shi-jian-by-le-e3yb/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.root = list(range(n))\n",
    "        self.setCount = n\n",
    "        self.size = [1] * n\n",
    "\n",
    "    def findRoot(self, node):\n",
    "        while self.root[node] != node:\n",
    "            self.root[node] = self.root[self.root[node]]\n",
    "            node = self.root[node]\n",
    "        return node\n",
    "    \n",
    "    def unite(self, node1, node2):\n",
    "        root1, root2 = self.findRoot(node1), self.findRoot(node2)\n",
    "        if root1 == root2:\n",
    "            return False\n",
    "        if self.size[root1] >= self.size[root2]:\n",
    "            bigRoot, smallRoot = root1, root2\n",
    "        else:\n",
    "            bigRoot, smallRoot = root2, root1\n",
    "        self.root[smallRoot] = bigRoot\n",
    "        self.size[bigRoot] += self.size[smallRoot]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        logs.sort(key=lambda x:x[0])\n",
    "        for t, x, y in logs:\n",
    "            uf.unite(x, y)\n",
    "            if uf.setCount == 1:\n",
    "                return t \n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.parents = [i for i in range(n)]\n",
    "        self.sizes = [1 for _ in range(n)]\n",
    "\n",
    "    def find(self, x) -> int:\n",
    "        tmp1 = self.parents[x]\n",
    "        if tmp1 == self.parents[tmp1]:\n",
    "            return tmp1\n",
    "\n",
    "        root = self.find(tmp1)\n",
    "        self.parents[x] = root  # optimize tree length\n",
    "        return root\n",
    "\n",
    "    def union(self, x, y) -> None:\n",
    "        tmp1, tmp2 = self.find(x), self.find(y)\n",
    "        if tmp1 == tmp2:  return\n",
    "\n",
    "        if self.sizes[tmp1] <= self.sizes[tmp2]:\n",
    "            self.parents[tmp1] = tmp2\n",
    "            self.sizes[tmp2] += self.sizes[tmp1]\n",
    "        else:\n",
    "            self.parents[tmp2] = tmp1\n",
    "            self.sizes[tmp1] += self.sizes[tmp2]\n",
    "        return\n",
    "\n",
    "class Solution:\n",
    "    def earliestAcq(self, logs: List[List[int]], n: int) -> int:\n",
    "        # uf\n",
    "        logs.sort()\n",
    "        uf = UnionFind(n)\n",
    "        for time, x, y in logs:\n",
    "            uf.union(x, y)\n",
    "            if uf.sizes[uf.find(x)] == n or uf.sizes[uf.find(y)] == n:\n",
    "                return time\n",
    "\n",
    "        return -1\n",
    "            \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
